Grokking Algorithm Complexity and Big-O
Rate this course
Ask Author
Contribute
Back to course home

0% completed

Vote For New Content
Introduction
Course Overview
Basics of Algorithm Analysis
Introduction to Algorithm Analysis
Measuring Efficiency
Functions and Their Growth Rates
Asymptotic Notations
Overview of Asymptotic Analysis
Big-O Notation (O-notation)
Big-Omega Notation (Ω-notation)
Big-Theta Notation (Θ-notation)
Little-o and Little-omega Notations
Comparing Asymptotic Notations
Time Complexity Analysis
Understanding Time Complexity
Analyzing Control Structures
Analyzing Simple Algorithms
Best, Worst, and Average Cases
Constant Time: O(1)
Linear Time: O(n)
Quadratic Time: O(n²)
Quiz
Space Complexity Analysis
Understanding Space Complexity
Analyzing Space Complexity of Algorithms
Constant Space: O(1)
Linear Space: O(n)
Quadratic Space: O(n²)
Quiz
Analyzing Recursive Algorithms
Introduction to Recursion
Recursion Tree Method
Recurrence Relation Method
Master Theorem Method
Space Complexity Analysis of Recursive Algorithm
Logarithmic Time and Space: O(log n)
Linearithmic Time: O(n log n)
Exponential Time and Space: O(2ⁿ)
Quiz
Data Structures and Complexity Analysis
Array
Linked List
Hash Table and Set
Stack and Queue
Binary Search Tree
Quiz
Sorting Algorithms
Graph Algorithms
Dynamic Programming Algorithms
Coding Interview Problems
Trade-offs in Algorithm Design
Binary Search Tree

A Binary Search Tree (BST) is a type of binary tree where each node has at most two children, and the tree maintains a specific order. For any given node:

  • The left subtree contains only nodes with values less than the node’s value.
  • The right subtree contains only nodes with values greater than the node’s value.

This property enables efficient searching, insertion, and deletion operations, making BSTs useful for various applications where ordered data needs to be stored and accessed quickly.

Image

Basic Operations on a BST and Their Complexity Analysis

1. Insertion

Java
. . . .

Time Complexity

  1. Insertion Process:

    • Traversal: The traversal path depends on the value of the key being inserted. The function will travel down one branch of the tree, either to the left or right, at each recursive step.
    • Number of Recursive Calls:
      • In a balanced BST, the height h of the tree is approximately , where n is the number of nodes. Therefore, the function will make up to recursive calls.
      • In an unbalanced BST (e.g., if the tree resembles a linked list), the height h can be as large as n. In this case, the function may make up to recursive calls.

Overall Time Complexity:

  • Average Case: for a balanced BST.
  • Worst Case: for an unbalanced BST (e.g., skewed tree).

Space Complexity

  1. Call Stack (Recursive Space):

    • The space complexity due to recursion is directly proportional to the maximum depth of the call stack.
    • In a balanced BST, the maximum depth of the recursive stack is .
    • In an unbalanced BST, the maximum depth can reach if the tree is skewed.
  2. Auxiliary Space:

    • The function itself does not use additional space apart from the recursion stack.

Overall Space Complexity:

  • Average Case: for a balanced BST.
  • Worst Case: for an unbalanced BST.
Java
. . . .

Time Complexity

  1. Search Process:
    • Traversal: At each recursive step, the function decides to move left (search(root.left, key)) or right (search(root.right, key)) based on the value of key relative to root.val.
    • Number of Recursive Calls:
      • In a balanced BST, the height h of the tree is approximately , where n is the number of nodes. The function will make up to recursive calls in this case.
      • In an unbalanced BST (e.g., if the tree is skewed), the height h can be up to n. The function may make up to recursive calls.

Overall Time Complexity:

  • Average Case: for a balanced BST.
  • Worst Case: for an unbalanced BST.

Space Complexity

  1. Call Stack (Recursive Space):

    • The space complexity due to recursion is directly proportional to the maximum depth of the call stack.
    • In a balanced BST, the maximum depth of the recursive stack is .
    • In an unbalanced BST, the maximum depth can reach if the tree is skewed.
  2. Auxiliary Space:

    • The function itself does not use any additional space beyond the call stack.

Overall Space Complexity:

  • Average Case: for a balanced BST.
  • Worst Case: for an unbalanced BST.

3. Deletion

Java
. . . .

Time Complexity

  1. Traversal and Search for the Node:

    • Number of Recursive Calls:
      • In a balanced BST, the traversal depth is , where n is the number of nodes in the tree.
      • In an unbalanced BST, the traversal depth can be up to if the tree is skewed.
  2. Deleting the Node:

    • Case 1: Node with No Children:
      • Directly removes the node by returning null.
      • Time Complexity: .
    • Case 2: Node with One Child:
      • The node is replaced by its single child.
      • Time Complexity: .
    • Case 3: Node with Two Children:
      • Finds the in-order successor (the smallest node in the right subtree) using the findMin method, and recursively deletes it.
      • Finding the In-order Successor: The findMin method traverses the leftmost path in the right subtree.
        • Time Complexity of findMin: , where h is the height of the tree.

Overall Time Complexity:

  • Average Case: for a balanced BST.
  • Worst Case: for an unbalanced BST, including finding and deleting the node.

Space Complexity

  1. Call Stack (Recursive Space):

    • The space complexity depends on the recursion depth, which is proportional to the height of the tree.
    • Balanced Tree: space for the recursive stack.
    • Unbalanced Tree: space for the recursive stack in the worst case.
  2. Auxiliary Space:

    • The findMin method does not use any additional space other than traversing nodes.

Overall Space Complexity:

  • Average Case: for balanced trees.
  • Worst Case: for unbalanced trees.
Stack and Queue
Quiz
Mark as Completed

On this page

Basic Operations on a BST and Their Complexity Analysis

  1. Insertion
  1. Search
  1. Deletion